import org.w3c.dom.ls.LSException;

import javax.management.MBeanAttributeInfo;
import java.util.Arrays;
import java.util.Random;

class MyListNode {

    public  ListNode head;

    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

//    public ListNode end;
    public void addFirst(int val) {//头插
        ListNode node = new ListNode(val);
        node.next = head;
        head = node;
    }

    public void addEnd(int val) {//尾插
        if (head == null) {
            addFirst(val);
        } else {
            ListNode tmp = head;
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = new ListNode(val);
        }
    }

    public void DelNode() {//尾删
        ListNode tmp = head;
        ListNode prev = head;
        if (tmp == null) {
            return;
        }
        if (size() == 1) {
            head = null;
            return;
        }
        while (tmp.next != null) {
            prev = tmp;
            tmp = tmp.next;
        }
         prev.next = null;
    }

    public void delHead() {
        if (head != null) {
            head = head.next;
        }
    }
    public void delAll(int target) {

        while (Contain(target)) {

            //找到这个节点
            ListNode tmp = head;
            ListNode prev = head;
            while (tmp.val != target && tmp != null) {
                prev = tmp;
                tmp = tmp.next;
            }
            //删除
            if (tmp == head) {
                delHead();
            }
            prev.next = tmp.next;
        }
    }

    public void clear() {
        this.head = null;
    }
    public  ListNode getNode(int val) {//得到值对应值的节点

        ListNode tmp = head;
        while (tmp != null) {
            if (tmp.val == val) {
                return tmp;
            }
            tmp = tmp.next;
        }
        return null;
    }

    public int size() {
        ListNode tmp = head;
        int count = 0;
        while (tmp != null) {
            count++;
            tmp = tmp.next;
        }
        return count;
    }

    public void show() {
        ListNode tmp = head;
        while (tmp != null) {
            System.out.print(tmp.val+" ");
            tmp = tmp.next;
        }
        System.out.println();
    }
    public void show(ListNode head) {
        ListNode tmp = head;
        while (tmp != null) {
            System.out.print(tmp.val+" ");
            tmp = tmp.next;
        }
        System.out.println();
    }

    public Boolean Contain(int val) {
        ListNode tmp = head;
        while (tmp != null) {
            if (tmp.val == val) {
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }

    //更改
    public boolean set(int target, int val) {
        ListNode tmp = head;
        while (tmp != null) {
            if (tmp.val == target) {
                tmp.val = val;//更改
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }
    //闭环的位置
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode faster = head;
        ListNode prev = head;
        while(faster != null &&faster.next != null){
            slow = slow.next;
            faster = faster.next.next;
            if(faster == slow){
                break;
            }
        }
        if(faster == null || faster.next == null){
            return null;
        }
        slow = head;
        while(slow != faster){
            slow = slow.next;
            faster = faster.next;
        }
        return slow;
    }
    //是否有闭环
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode faster = head;
        while(faster != null &&faster.next != null){
            slow = slow.next;
            faster = faster.next.next;
            if(faster == slow){
                return true;
            }
        }
        return false;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tmp1 = headA;
        ListNode tmp2 = headB;

        while(tmp1 != tmp2){
            tmp1 = tmp1==null?headB:tmp1.next;
            tmp2 = tmp2==null?headA:tmp2.next;
        }
        return tmp1;
    }
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode prev = head;
        ListNode new_end = head;
        ListNode cur = prev.next;
        ListNode tmp = cur;
        if (cur != null) {
            tmp = cur.next;
        }
        while (cur != null) {
            cur.next = prev;
            prev = cur;
            cur = tmp;
            if (tmp != null)
                tmp = tmp.next;
        }
        new_end.next = null;
        return prev;
    }
    public boolean IsReverseList(ListNode listNode) {
        ListNode slow = listNode;
        ListNode faster = listNode;
        if (slow == null) {
            return true;
        }
        //得到中间节点slow
        while (faster != null && faster.next != null) {
            slow = slow.next;
            faster = faster.next.next;
        }

        ListNode cur = slow.next;
        while (cur != null) {//反转
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }
        ListNode tmp = head;
        while (slow != tmp) {
            if (tmp.val != slow.val) {
                return false;
            }
            if (tmp.next == slow) {
                return true;
            }
            slow = slow.next;
            tmp = tmp.next;
        }
        return true;
    }

    public boolean hasCycle(MyListNode listNode) {
        ListNode slow = listNode.head;
        ListNode fast = listNode.head;
        while (slow != fast) {
            if (fast == null && fast.next !=null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    public ListNode middleNode() {
        ListNode slow = head;
        ListNode faster = head;
        while (faster != null && faster.next != null) {
            slow = slow.next;
            faster = faster.next.next;
        }
        return slow;
    }

    //合并俩个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list2 == null) {
            return list1;
        }
        if (list1 == null) {
            return list2;
        }
        ListNode tmp1 = list1;
        ListNode tmp2 = list2;
        ListNode prev = null;
        while (tmp1 != null && tmp2 != null) {
            if (tmp1.val >= tmp2.val) {//头插进入tmp1
                ListNode tmp = tmp2.next;
                if (prev != null) {//从中间查
                    prev.next = tmp2;
                    tmp2.next = tmp1;
                    tmp1 = tmp2;
                }else{//从头插入
                    tmp2.next = tmp1;
                }
                if (tmp1 == list1) {
                    list1 = tmp2;//更新list1的头节点
                    prev = list1;
                }
                tmp2 = tmp;
            } else {
                prev = tmp1;
                tmp1 = tmp1.next;
            }
        }
        if (tmp2 != null) {
            prev.next = tmp2;
        }
        return list1;
    }

    //将比x小的放在前面
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode head_s = null;//小的头节点
        ListNode head_b = null;//大的头节点
        ListNode small = null;//小于
        ListNode big = null;//大于等于
        ListNode tmp = pHead;//用这个来遍历pHead
        while (tmp != null) {
            if (tmp.val < x) {
                if (small == null) {
                    small = new ListNode(tmp.val);
                    head_s = small;
                } else {
                    small.next = new ListNode(tmp.val);
                    small = small.next;
                }
            } else {
                if (big == null) {
                    big = new ListNode(tmp.val);
                    head_b = big;
                } else {
                    big.next = new ListNode(tmp.val);
                    big = big.next;
                }
            }
            tmp = tmp.next;
        }
        if (small != null) {
            small.next = head_b;
            return head_s;
        } else
            return head_b;
    }

    public ListNode removeElements(ListNode head, int val) {
        ListNode prev = head;
        ListNode cur = head;
        while(cur != null){
            prev = head;
            cur = head;
            //找到val
            while(cur != null&&cur.val!=val){
                prev = cur;
                cur = cur.next;
            }
            if(cur == head){
                head = head.next;
                cur = head;
            }else{
                if (cur == null) {
                    prev.next = cur;
                } else {

                    prev.next = cur.next;
                }
            }
        }
        return head;
    }        @Override
    public String toString() {
        ListNode Head = this.head;
        StringBuilder tmp = new StringBuilder();
        while (Head != null) {
            tmp.append(Head.val);
            tmp.append(" ");
            Head = Head.next;
        }
        String end = tmp.toString();
            return "MyListNode{" +
                      end +
                    '}';
    }
}

public class class_study {

    public static void main(String[] args) {
        MyListNode hh = new MyListNode();
        for (int i = 10; i > 0; i--) {
            hh.addEnd(i);
        }
        hh.show(hh.partition(hh.head, 5));
    }
    public static void maiAn(String[] args) {
        MyListNode hh = new MyListNode();
        hh.addEnd(1);
        hh.addEnd(2);
        hh.addEnd(1);
        hh.addEnd(1);
        hh.removeElements(hh.head, 1);
    }
    public static void main11(String[] args) {
        MyListNode hh = new MyListNode();
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            int r = random.nextInt(1000 - 1 + 1) + 1;//1-1000
            hh.addEnd(r);
        }
        hh.show();
        MyListNode.ListNode hhh = hh.partition(hh.head, 400);
        hh.show(hhh);
    }

    public static void mainm1(String[] args) {
        MyListNode one = new MyListNode();
        MyListNode two = new MyListNode();
        one.addEnd(5);
        two.addEnd(1);
        two.addEnd(3);
        two.addEnd(4);
        one.show(one.mergeTwoLists(one.head, two.head));

    }

    public static void mai1n(String[] args) {
        //toString
        MyListNode hh = new MyListNode();
        System.out.println(hh);
        System.out.println(hh.middleNode().val);
    }

    public static void main4(String[] args) {
        MyListNode hh = new MyListNode();
        for (int i = 1; i <= 6; i++) {
            hh.addEnd(i);
        }
        hh.show();
        MyListNode.ListNode tmp = hh.reverseList(hh.head);
        hh.show(tmp);
        hh.clear();
        hh.addEnd(1);
        hh.addEnd(2);
        hh.show();
        MyListNode.ListNode tmp1 = hh.reverseList(hh.head);
        System.out.println(tmp1);
        System.out.println("hh");
        hh.clear();
        hh.addEnd(1);
        System.out.println(hh.reverseList(hh.head));
    }

    public static void mainm(String[] args) {
        MyListNode hh = new MyListNode();
        for (int i = 0; i < 5; i++) {
            hh.addEnd(i);
        }
        hh.addEnd(1);
        hh.addEnd(1);
        hh.addEnd(1);
        hh.addEnd(1);
        hh.addFirst(0);
        hh.addFirst(0);
        hh.addFirst(0);
        hh.addFirst(0);
        hh.show();
        hh.delAll(1);
        hh.delAll(0);
        hh.show();
    }

    public static void maina(String[] args) {
        MyListNode hh = new MyListNode();
        hh.addEnd(1);
        hh.addEnd(11);
        hh.addEnd(11);
        hh.addEnd(1);
        hh.show();
//        System.out.println(hh.IsReverseList(hh));
        hh.DelNode();
        hh.DelNode();
        hh.DelNode();
        hh.DelNode();
        hh.show();
        System.out.println(hh.IsReverseList(hh.head));
    }

    public static void mainmm(String[] args) {
        MyListNode hh = new MyListNode();
        for (int i = 0; i < 4; i++) {
            hh.addEnd(i);
        }
        hh.show();
        System.out.println(hh.size());
    }

}
